#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    bool exist(vector<vector<char>> &board, string word)
    {
        vector<vector<bool>> visited;
        visited.resize(board.size(), vector<bool>(board[0].size(), false));
        for (int x = 0; x < board.size(); x++)
        {
            for (int y = 0; y < board[0].size(); y++)
            {
                if (board[x][y] == word[0])
                {
                    if (dfs(board, visited, word, x, y))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &board, vector<vector<bool>> &visited, string &word, int x, int y)
    {
        if (word.empty())
        {
            return true;
        }
        if (x < 0 || x >= board.size() || y < 0 || y >= board[x].size() || board[x][y] != word[0])
        {
            return false;
        }
        if (visited[x][y] || board[x][y] != word[0])
        {
            return false;
        }
        visited[x][y] = true;
        string res = word.substr(1);
        if (dfs(board, visited, res, x + 1, y) || dfs(board, visited, res, x - 1, y) || dfs(board, visited, res, x, y + 1) || dfs(board, visited, res, x, y - 1))
        {
            return true;
        }
        visited[x][y] = false;
        return false;
    }
};

int main()
{
    cout << "Code79" << endl;
    Solution s;
    vector<vector<char>> board{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
    string word = "ABCCED";
    cout << boolalpha << s.exist(board, word);
    return 0;
}